package com.bwt.linkedList;

import java.util.Stack;

public class SingleLinkedListDemo {
	public static void main(String[] args) {
		//测试一下
		//1.创建节点
		HeroNode hero = new HeroNode(1, "宋江", "及时雨");
		HeroNode hero2 = new HeroNode(3, "卢俊义", "玉麒麟");
		HeroNode hero3 = new HeroNode(2, "吴用", "智多星");
		HeroNode hero4 = new HeroNode(7, "公孙胜", "入云龙");
		HeroNode hero5 = new HeroNode(9, "关胜", "大刀");


		HeroNode h = new HeroNode(2, "宋江", "及时雨");
		HeroNode h2 = new HeroNode(4, "卢俊义", "玉麒麟");
		HeroNode h3 = new HeroNode(6, "吴用", "智多星");
		HeroNode h4 = new HeroNode(8, "公孙胜", "入云龙");
		HeroNode h5 = new HeroNode(10, "关胜", "大刀");


		//创建一个链表
		SingleLinkedList singk = new SingleLinkedList();
		SingleLinkedList singk2 = new SingleLinkedList();

		//添加数据到链表
		singk.add(hero);
		singk.add(hero2);
		singk.add(hero5);
		singk.addByOrder(hero3);
		singk.addByOrder(hero4);

		singk2.addByOrder(h);
		singk2.addByOrder(h3);
		singk2.addByOrder(h2);
		singk2.addByOrder(h4);
		singk2.addByOrder(h5);






		//修改节点
		singk.update(new HeroNode(2, "小卢", "小玉麒麟"));

		singk.delete(3);

		System.out.println("有效的节点个数==" + singk.getLength(singk.getHead()));
		System.out.println(singk.findLastIndex(singk.getHead(), 1).toString());
		//显示链表
		singk.list();

		System.out.println("逆序打印原链表");
		singk.reversePrint(singk.getHead());

		System.out.println("合并两个有序链表");
		singk.merge(singk,singk2).list();
	}
}

//定义singleLinkedList  用于管理英雄节点

class SingleLinkedList {
	// 初始化一个头节点 头节点不要动
	HeroNode head = new HeroNode(0, "", "");

	public SingleLinkedList(HeroNode head) {
		this.head = head;
	}

	public SingleLinkedList() {
	}

	public HeroNode getHead() {
		return head;
	}

	public void add(HeroNode heroNode) {
		// 当不考虑编号的顺序时,
		// 找到当前链表的最后,
		// 然后将这个节点的next节点指向传入的节点
		HeroNode temp = head;
		// 遍历链表
		//temp.next == null 说明 此时temp已经位于链表的最后
		while (temp.next != null) {

			// 没有找到 就将temp后移一位
			temp = temp.next;
		}
		//当循环退出时, temp 已经指向了链表的最后
		temp.next = heroNode;
	}

	public void list() {
		// 判断是否为空
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		// 头节点 不能动, 所以需要一个辅助变量
		HeroNode temp = head;
		while (temp != null) {
			System.out.println(temp.toString());
			temp = temp.next;
		}
	}

	public void update(HeroNode heroNode) {
		if (head.next == null) {
			System.out.println("链表为空");
		}
		HeroNode temp = head;
		boolean flag = false;
		while (true) {
			if (temp == null) {
				break;
			}
			if (temp.no == heroNode.no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.name = heroNode.name;
			temp.nickName = heroNode.nickName;
		} else {
			System.out.printf("没有找到编号为 %d 的节点.\n", heroNode.no);
		}
	}

	public void delete(int no) {
		HeroNode temp = head;
		boolean flag = false;
		while (true) {
			if (temp.next == null) {
				break;
			}
			if (temp.next.no == no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}

		if (flag) {
			//将next的next temp的next 相当于原本temp.next被删除了
			temp.next = temp.next.next;
		} else {
			System.out.printf("要删除的节点 %d 不存在。\n", no);
		}

	}

	public void addByOrder(HeroNode heroNode) {
		HeroNode temp = head;
		boolean flag = false;    //标识添加的编号是否存在，默认为false
		while (true) {
			if (temp.next == null) {
				break;
			}
			if (heroNode.no < temp.next.no) {
				break;
			}
			if (heroNode.no == temp.next.no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			System.out.printf("准备插入的英雄编号%d已经存在了。无法加入\n", heroNode.no);
		} else {
			// 插入到链表中 temp后面
			/*
			 * 1. 此时node 应该插入temp和temp.next 中间
			 * 2. temp 为head 链表中节点的引用
			 * 3. 因为temp指针指向的节点的下一个节点的编号比要插入的大
			 * 4. 所以将heroNode的next的引用指向原temp的next节点
			 * 5. 然后将原temp的next引用指向heroNode
			 * */
			heroNode.next = temp.next;
			temp.next = heroNode;
		}

	}

	public int getLength(HeroNode head) {
		if (head.next == null) {
			return 0;
		}
		int length = 0;
		HeroNode temp = head.next;
		while (temp != null) {
			length++;
			temp = temp.next;
		}
		return length;
	}

	public HeroNode findLastIndex(HeroNode head, int index) {
		if (head.next == null) {
			return null;
		}
		int size = getLength(head);
		if (size <= 0 || index > size) {
			return null;
		}
		HeroNode cur = head.next; //3 //3-1 = 2
		for (int i = 0; i < size - index; i++) {
			cur = cur.next;
		}
		return cur;
	}

	public void reversedList(HeroNode head) {
		// 如果链表为空 或者链表只有一个节点 直接返回
		if (head.next == null || head.next.next == null) {
			return;
		}

		//1. 定义一个辅助指针(变量) , 用于遍历原来的链表
		HeroNode temp = head.next;
		//定义一个next空节点 用于指向指针的下一个节点
		HeroNode next = null;
		HeroNode reverseHead = new HeroNode(0, "", "");
		//2.遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
		while (temp != null) {
			//先暂时保存当前节点的下一个节点，因为后面需要使用
			next = temp.next;
			//将新链表的最前端 指向指针的后面
			temp.next = reverseHead.next;
			//将 指针指向新链表的头的后面
			reverseHead.next = temp;
			// 将指针后移
			temp = next;
		}
		//将新链表的的第一个节点, 指向原head链表的第一个节点 , 实现单链表的反转
		head.next = reverseHead.next;
	}

	//使用stack方式 实现逆序打印
	public void reversePrint(HeroNode head) {
		if (head.next == null) {
			return;
		}
		// 创建stack  将各个节点加入栈
		Stack<HeroNode> stack = new Stack<>();
		HeroNode temp = head.next;
		while (temp != null) {
			stack.push(temp);
			temp = temp.next;
		}
		while (stack.size() > 0) {
			System.out.println(stack.pop());
		}
	}

	public SingleLinkedList merge(SingleLinkedList list1, SingleLinkedList list2) {
		if (list1.head.next == null) {
			return list2;
		} else if (list2.head.next == null) {
			return list1;
		}
		HeroNode newNode = new HeroNode();
		HeroNode n1 = newNode;
		HeroNode l1 = list1.head.next;
		HeroNode l2 = list2.head.next;
		while (l1 != null && l2 != null) {
			if (l1.no < l2.no) {
				//如果l1 < l2 将l1放到辅助指针n1后面
				//将 l1 和 n1 后移
				// 在进行第二次循环 此时循环的是第二个l1 和 第一个l2 比较
				// l2 大 则 将l2放到辅助指针n1后面 在将 l2 和 n1 后移
				// 当l1 和l2 有一个等于空时退出循环时, 说明其中一个链表已经遍历完毕
				// 则需要将将另一个链表的尾部接在n1 后面
				// 因为合并的是两个有序链表 所以不会出现l2 > l1 的问题 最多相等的情况也是进入到else中 先后放入l2和l1
				// 最后则返回n1的原链表 newnode即可
				n1.next = l1;
				l1 = l1.next;
				n1 = n1.next;
			} else {
				n1.next = l2;
				l2 = l2.next;
				n1 = n1.next;
			}
		}
		if (l1 == null) {
			n1.next = l2;
		}
		if (l2 == null) {
			n1.next = l2;

		}
		return new SingleLinkedList(newNode);
	}

}

//定义heroNode 每个heroNode 就是一个节点
class HeroNode {
	public int no;
	public String name;
	public String nickName;
	public HeroNode next;

	public HeroNode(int no, String name, String nickName) {
		this.no = no;
		this.name = name;
		this.nickName = nickName;
	}

	public HeroNode() {
	}

	@Override
	public String toString() {
		return "HeroNode{" +
				"no=" + no +
				", name='" + name + '\'' +
				", nickName='" + nickName + '\'' +
				'}';
	}
}
